package com.zy.tree;

import java.util.Objects;

/**
 * @author zhaoyi
 * @date 2021/8/10 17:37
 * 简单的二叉树
 * <p>
 * * 在树中的任意一个节点，
 * * 其左子树中的每个节点的值，都要小于这个节点的值，
 * * 而右子树节点的值都大于这个节点的值。
 */
public class BinaryTree<T extends Comparable<? super T>> {

    private T data;
    private BinaryTree<T> left;
    private BinaryTree<T> right;


    //插入数据
    public void put(T t) {
        put(this, t);
    }

    //查找
    public BinaryTree find(T t) {
        return find(this, t);
    }

    //中序遍历(中序遍历二叉查找树，可以输出有序的数据时间复杂度是 O(n))
    public void inOrder() {
        inOrder(this);
    }

    /**
     * 1 如果要删除的节点没有子节点，
     * 只需要直接将父指向为null
     * 2 如果要删除的节点只有一个子节点
     * 我们只需要将父节点指向要删除节点的子节点就可以。
     * 2 如果要删除的节点有两个子节点
     * 节点的右子树中的最小节点，把它替换到要删除的节点上。
     * 然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点）
     * 所以，我们可以应用上面两条规则来删除这个最小节点。
     */
    public void delete(T t) {
        delete(null, this, t, this.data.compareTo(t));
    }

    private void delete(BinaryTree parent, BinaryTree tree, T t, int pc) {
        if (tree == null) {
            throw new RuntimeException("无对应数据: " + t);
        }
        int compare = tree.getData().compareTo(t);

        //找到了
        if (compare == 0) {
            if (tree.getRight() == null && tree.getLeft() == null) {
                if (parent == null) {
                    tree.setData(null);
                    return;
                }
                //1 如果要删除的节点没有子节点，
                // 只需要直接将父指向为null
                if (pc > 0) {
                    parent.setLeft(null);
                } else {
                    parent.setRight(null);
                }
            } else if (tree.getRight() == null) {
                if (parent == null) {
                    tree.setData(tree.getLeft().getData());
                    tree.setLeft(tree.getLeft().getLeft());
                    tree.setRight(tree.getLeft().getRight());
                    return;
                }

                //2 如果要删除的节点只有一个子节点
                //我们只需要将父节点指向要删除节点的子节点就可以
                if (pc > 0) {
                    parent.setLeft(tree.getLeft());
                } else {
                    parent.setRight(tree.getLeft());
                }



            } else if (tree.getLeft() == null) {
                if (parent == null) {
                    tree.setData(tree.getRight().getData());
                    tree.setLeft(tree.getRight().getLeft());
                    tree.setRight(tree.getRight().getRight());
                    return;
                }
                //2 如果要删除的节点只有一个子节点
                //我们只需要将父节点指向要删除节点的子节点就可以

                if (pc > 0) {
                    parent.setLeft(tree.getRight());
                } else {
                    parent.setRight(tree.getRight());
                }
            }else {
                //如果要删除的节点有两个子节点
                //节点的右子树中的最小节点，把它替换到要删除的节点上。
                //然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点）
                //所以，我们可以应用上面两条规则来删除这个最小节点。
                BinaryTree<T> min =  minNode(tree.getRight());
                tree.setData(min.getData());
                delete(tree,tree.getRight(),min.getData(),-1);
            }

        } else if (compare > 0) {
            delete(tree, tree.getLeft(), t, compare);
        } else {
            delete(tree, tree.getRight(), t, compare);
        }


    }

    private BinaryTree<T> minNode(BinaryTree<T> right) {
        BinaryTree min = right;
        while (min.getLeft() != null){
            min = min.getLeft();
        }
        return min;
    }


    private BinaryTree find(BinaryTree tree, T t) {
        if (tree == null) {
            return null;
        }
        if (tree.getData().compareTo(t) == 0) {
            return tree;
        } else if (tree.getData().compareTo(t) > 0) {
            return find(tree.getLeft(), t);
        } else {
            return find(tree.getRight(), t);
        }
    }


    private void put(BinaryTree<T> tree, T t) {
        if (tree.data == null) {
            tree.setData(t);
            return;
        }

        if (t.compareTo(tree.data) < 0) {
            BinaryTree<T> left = tree.getLeft();
            if (left == null) {
                tree.setLeft(new BinaryTree<>());
            }
            put(tree.getLeft(), t);
        } else {
            BinaryTree<T> right = tree.getRight();
            if (right == null) {
                tree.setRight(new BinaryTree<>());
            }
            put(tree.getRight(), t);
        }
    }

    private void setData(T data) {
        this.data = data;
    }

    public BinaryTree<T> getLeft() {
        return left;
    }

    public BinaryTree<T> getRight() {
        return right;
    }

    private void setLeft(BinaryTree<T> left) {
        this.left = left;
    }

    private void setRight(BinaryTree<T> right) {
        this.right = right;
    }


    //递归 inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
    private void inOrder(BinaryTree t) {
        if (t == null) {
            return;
        }
        inOrder(t.getLeft());
        System.out.print(t.getData() + "  ");
        inOrder(t.getRight());
    }

    public T getData() {
        return data;
    }


    @Override
    public String toString() {
        return Objects.toString(data);
    }
}
